/**
 * Created by L.jp
 * Description:输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，
 * 子数组最小长度为1。求所有子数组的和的最大值。
 * User: 86189
 * Date: 2022-09-01
 * Time: 16:07
 */
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
//        if(array.length==1) {
//            return array[0];
//        }
//        int len=array.length;
//        //dp[i]表示i位置的连续子数组的最大和
//        int[] dp=new int[len];
//        //初始化，0位置的最大和就是他本身
//        dp[0]=0;
//        //最大和初始化为第一个元素
//        int maxSum=dp[0];
//        for(int i=1;i<len;i++){
//            //i位置的连续子数组最大和就是看他前一个位置的最大和，以及该位置本身的值，两个值谁更大
//            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
//            //更新最终的最大值
//            maxSum=Math.max(maxSum,dp[i]);
//        }
//        return maxSum;
        
        //优化，由于i位置的最大和至于i-1位置有关，没有使用整个数组的关系，所以可以使用变量来代替上面dp[i]的信息
        //优化就是用两个变量取代dp[i]和的dp[i-1]
        //x就代替dp[i-1]表示前一个位置的最大和，初始为array[0];
        int x=array[0];
        //y代替dp[i],表示当前位置的最大和
        int y=0;
        int  maxSum=x;
        for(int i=1;i<array.length;i++){
            //求得每一个位置的连续子数组最大和，要么是前一个位置的最大和+当前位置的值，要么就是当前值
            y=Math.max(x+array[i],array[i]);
            //更新最终的最大值
            maxSum=Math.max(maxSum,y);
            //更新前一个的连续子数组最大和
            x=y;
        }
        return maxSum;
    }
}
